# 实现一个LRU缓存
# 前置实现 DoubleList 双向链表 保证Lru缓存的插入 O（1）
class Node():
    def __init__(self,key,value):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None
class DoubleList:
    def __init__(self):
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0
    # 链表尾部插入节点 -》 最近使用
    def addLast(self,node):
        temp = self.tail.prev
        temp.next = node
        node.next = self.tail
        self.tail.prev = node
        node.prev = temp
        self.size += 1


    # 链表删除元素
    def remove(self,node):
        p  = node.prev
        n  = node.next
        p.next = n
        n.prev = p
        self.size -= 1
    # 链表头部删除元素 -> 淘汰最久使用
    def removeFirst(self):
        if self.size == 0:
            return None
        first = self.head.next
        self.remove(first)
        return first

    # 查看链表的长度
    def size(self):
        return self.size